P4778 Counting swaps

对于每个位置 ii , 我们向 pip_i 连一条边。 结合题意可知,一个合法的排列,是一个由 nn 个自环组成的图。

但现在会形成多个环,不妨记环的数量为 kk , 第 ii 个环的大小为 sis_i(包括自环)。

我们现在要做的,就是将这 kk 个环拆成 nn 个自环。

显然,对于一个大小为 ss 的环,拆成自环至少需要 s1s-1次操作。

wn(x,y)w_n(x,y) , 表示将 nn 个点的环 , 拆成 xx 个点的环 + yy个点的环的方案数。

显然有

wn(x,y)={n2x=ynx=y(x+y=n)w_n(x,y)= \begin{cases} \frac{n}{2} & x=y\\ n & x \not= y \end{cases} (x+y=n)

fnf_n 表示大小为 nn 的环的拆分方案数(f1=1f_1=1) , 则根据多重集的排列公式得:

fn=x+y=nxn2wn(x,y)×fx×fy×(n2)!(x1)!(y1)!f_n=\sum_{x+y=n}^{x \le\frac{n}{2}}w_n(x,y) \times f_x \times f_y \times \frac{ (n-2)! }{(x-1)! (y-1)!}

这样递推的复杂度是 Θ(n2)\Theta(n^2) 的 ,给一份代码:

f[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ ) {
		for( int x = 1 ; x <= i / 2 ; x ++ ) {
			int y = i - x , t = x == y ? i / 2 : i;
			f[ i ] += t * f[ x ] * f[ y ] * ( Fac[ i - 2 ] / Fac[ x - 1 ] / Fac[ y - 1 ] );
		}
		printf("%d %d\n", i , f[ i ] );
	}

经过找规律,我们发现,fi=ii2f_i=i^{i-2},现在就可以Θ(nlogn)\Theta(nlogn)求出fif_i了。

答案也是一个多重集,可以简单求出

Ans=(i=1kf[si])×((nk)!i=1k(si1)!)Ans=(\prod_{i=1}^k f[s_i]) \times (\frac{(n-k)!}{\prod_{i=1}^k(s_i-1)!})

#include <cstdio>
#include <cstring>
using namespace std;
#define Mod 1000000009

const int MAXN = 100000;
int t , n , p[ MAXN + 5 ] , s[ MAXN + 5 ] , k;
bool vis[ MAXN + 5 ];

int Quick_pow( int x , int po ) {
	int Ans = 1;
	while( po ) {
		if( po % 2 ) Ans = 1ll * Ans * x % Mod;
		x = 1ll * x * x % Mod;
		po /= 2;
	}
	return Ans;
}
int Inv( int x ) {
	return Quick_pow( x , Mod - 2 );
} 

int dfs( int u ) {
	if( vis[ u ] ) return 0;
	vis[ u ] = 1;
	return dfs( p[ u ] ) + 1;
}

int f[ MAXN + 5 ] , Fac[ MAXN + 5 ] , InvFac[ MAXN + 5 ];
void Init( ) {
	f[ 1 ] = 1;
	for( int i = 2 ; i <= MAXN ; i ++ )
		f[ i ] = Quick_pow( i , i - 2 );
	
	Fac[ 0 ] = 1; 
	for( int i = 1 ; i <= MAXN ; i ++ )
		Fac[ i ] = 1ll * Fac[ i - 1 ] * i % Mod;
		
	InvFac[ MAXN ] = Inv( Fac[ MAXN ] );
	for( int i = MAXN - 1 ; i >= 0 ; i -- )
		InvFac[ i ] = 1ll * InvFac[ i + 1 ] * ( i + 1 ) % Mod;
}
int main( ) {
	Init( ); 
	scanf("%d",&t);
	while( t -- ) {
		k = 0;
		memset( vis , 0 , sizeof( vis ) );
		memset( s , 0 , sizeof( s ) );
		
		scanf("%d",&n);
		for( int i = 1 ; i <= n ; i ++ )
			scanf("%d",&p[ i ]);
		for( int i = 1 ; i <= n ; i ++ )
			if( !vis[ i ] ) s[ ++ k ] = dfs( i );
		
		int p1 = 1 , p2 = 1 , p3 = Fac[ n - k ];
		for( int i = 1 ; i <= k ; i ++ ) {
			p1 = 1ll * p1 * f[ s[ i ] ] % Mod;
			p2 = 1ll * p2 * Fac[ s[ i ] - 1 ] % Mod;
		}
		printf("%d\n", 1ll * p1 * Inv( p2 ) % Mod * p3 % Mod );
	}
	return 0;
}